package leetcode.code600;

public class Solution2 extends Solution600 {

	private final char ZERO = '0';
	private final char ONE = '1';

	@Override
	public int findIntegers(int n) {
		String str = Integer.toBinaryString(n);
		char[] max = str.toCharArray();
		char[] chars = new char[str.length()];
		int rst[][] = new int[chars.length][2];
		if (max[0] == '1') {
			rst[0][1] = 1;// 选1，累计有几种
		}
		rst[0][0] = 1;// 选0，累计有几种
		for (int i = 1; i < chars.length; i++) {
			rst[i][1] = rst[i - 1][0];
			rst[i][0] = rst[i - 1][0] + rst[i - 1][1];
			if ((i & 1) == 0 && max[i] == '0' && max[i - 1] == '0') {
				rst[i][1]--;
			}
		}
		return rst[chars.length - 1][0] + rst[chars.length - 1][1];
	}

	private int findIntegers(int index, int lastIndex, char[] chars, char[] max, boolean lastMatchMax) {
		if (index == chars.length) {
			return 1;
		}
		int ans = 0;
		chars[index] = ZERO;
		boolean indexMatch = lastMatchMax ? chars[index] == max[index] : false;
		ans += findIntegers(index + 1, index, chars, max, indexMatch);
		if (lastIndex == -1 || (!lastMatchMax && chars[lastIndex] == ZERO)
				|| (lastMatchMax && chars[lastIndex] == ZERO && max[index] == ONE)) {
			chars[index] = ONE;
			indexMatch = lastMatchMax ? chars[index] == max[index] : false;
			ans += findIntegers(index + 1, index, chars, max, indexMatch);
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
//		so.debug1();
//		so.debug2();
//		so.debug3();

		for (int i = 0; i < 100; i++) {
			int r = so.findIntegers(i);
			System.out.println(i + " " + r + " " + Integer.toBinaryString(i));
		}
//		int r = so.findIntegers(4);
//		System.out.println(4 + " " + r);
	}

}
